# 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一
# 个。 
# 
#  给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。 
# 
#  示例 1: 
# 
#  输入: 
#     2
#    / \
#   2   5
#      / \
#     5   7
# 
# 输出: 5
# 说明: 最小的值是 2 ，第二小的值是 5 。
#  
# 
#  示例 2: 
# 
#  输入: 
#     2
#    / \
#   2   2
# 
# 输出: -1
# 说明: 最小的值是 2, 但是不存在第二小的值。
#  
#  Related Topics 树 
#  👍 101 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def findSecondMinimumValue(self, root: TreeNode) -> int:

        # 计算树的第二小的数
        # 该 二叉树的特点 ：
        # 如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
        # 如果节点的值比最小值大，那么就是该节点
        # 否则 看左子树的最小值 和右子树的最小值
        def dfs(root, val):
            if not root:
                return -1

            if root.val > val:
                return root.val

            l = dfs(root.left, val)
            r = dfs(root.right, val)

            if l == -1:
                return r

            if r == -1:
                return l

            return min(l, r)

        return dfs(root, root.val)
# leetcode submit region end(Prohibit modification and deletion)
